﻿

namespace LeetCodePractice.Topic
{
    public class T00029_Divide : ITestBase
    {
        public void Test()
        {
            var action = (int num1, int num2) =>
            {
                var res = Divide(num1, num2);
                System.Console.WriteLine($"{num1}\\{num2} ={res}");
            };
            //action(1, 2);
            //action(2, 2);
            //action(-1, 2);
            action(-1021989372,- 82778243);
        }
        /// <summary>
        /// 用2^i2 
        /// </summary>
        /// <param name="dividend"></param>
        /// <param name="divisor"></param>
        /// <returns></returns>
        public int Divide(int dividend, int divisor)
        {
            // 溢出情况
            if (dividend == int.MinValue && divisor == -1)
            {
                return int.MaxValue;
            }

            // 记录结果的符号
            int sign = -1;
            if ((dividend > 0 && divisor > 0) || (dividend < 0 && divisor < 0))
            {
                sign = 1;
            }

            // 全部转换成负数，防止溢出
            dividend = dividend > 0 ? -dividend : dividend;
            divisor = divisor > 0 ? -divisor : divisor;

            int ans = 0;

            // 倍乘法，注意都是负数了，比较的时候与正数相反
            // 简单点理解，就是每次减去除数的 2^x 倍数，剩下的部分继续按这样的规则继续
            while (dividend <= divisor)
            {
                int tmp = divisor, count = 1;
                // 这里注意不要写成 tmp + tmp >= dividend，这样写加法有可能会溢出导致死循环
                while (tmp >= dividend - tmp)
                {
                    // tmp 和 count 每次增加一倍，所以叫倍增
                    tmp += tmp;
                    count += count;
                }
                // 被除数减去除数的 2^x 倍数做为新的被除数
                dividend -= tmp;
                // count 即 2^x
                ans += count;
            }

            return sign < 0 ? -ans : ans;
        }
    }
}
